18. 四数之和

一、题目原型：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。

二、题目意思剖析：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

三、解题思路：

从二元组。。。三元组。。。现在终于到了四元组。。。。
其实不管是多少元组，都是一样的方法。到最后都转换到left和right两个指针来控制后两位数字。
详细思路具体请参考：15. 三数之和、16. 最接近的三数之和

/**
 思路：和三元组相似。我们需要找到 a+b+c+d = t
 */
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
    
    // 二元组。。。三元组。。。终于到了四元组。。。。
    if nums.count < 4 {
        return []
    }
    else if nums.count == 4 {
        
        if nums[0] + nums[1] + nums[2] + nums[3] == target {
            return [nums]
        }else {
            return []
        }
    }
    else {
        let tempNums: [Int] = nums.sorted{$0<$1}
        let count = tempNums.count
        var fourSum: [[Int]] = Array.init()
        print(tempNums)
        for indexF in 0 ..< count-3 {
            // 剔除首位相同的元素
            if (indexF != 0) && (tempNums[indexF] == tempNums[indexF - 1]){
                continue
            }
            for indexH in indexF + 1 ..< count-2 {
                
                // 剔除第二位相同的元素，添加判断当 indexH 和 indexF不相邻时/
                if (indexH != 0) && (tempNums[indexH] == tempNums[indexH - 1]) && indexH - 1 != indexF  {
                    continue
                }
                
                let tempArray = self.aFunction(numbers: tempNums, begin: indexH + 1, end: count)
                print(tempArray)
                var left:Int = 0
                var right:Int = tempArray.count - 1
                while left < right {
                    // 临时的四个数字之和。
                    let tempTarget = tempNums[indexF] + tempNums[indexH] + tempArray[left] + tempArray[right]
                    print(tempTarget)
                    // 让tempTarget和目标值 target进行比对
                    if tempTarget == target {
                        let tempFourSum = [tempNums[indexF],tempNums[indexH],tempArray[left],tempArray[right]]
                        fourSum .append(tempFourSum)
                        
                        // 如果两个数字相同，我们直接跳到下一个循环。
                        while left < right && tempArray[left] == tempArray[left+1] {
                            left = left + 1
                        }
                        // 如果两个数字相同，我们直接跳到下一个循环。
                        while left < right && tempArray[right] == tempArray[right-1] {
                            right = right - 1
                        }
                        left = left + 1
                        right = right - 1
                    }
                    if tempTarget < target && left < right{
                        left = left + 1
                    }else if tempTarget > target && left < right{
                        right = right - 1
                    }
                }
            }
        }
        return fourSum
    }
}
func aFunction(numbers: Array<Int>, begin: Int, end: Int) -> Array<Int> {
    let newNumbers = Array(numbers[begin..<end])
    return newNumbers
}

四、小结

耗时220毫秒，超过71.43%的提交记录，总提交数282。

本题和15. 三数之和、16. 最接近的三数之和都可归为一类处理，如果有困惑的地方可以前后看看这几篇文章哦，解题思路差不多。

小哥哥小姐姐们有其他好的方法请留言哦，有困惑的地方也非常乐意一起探讨呢。😄!